package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 677. 键值映射
 * 使用Tire前缀树
 *
 * @author fy
 * @date 2022/4/18 21:34
 */
public class Solution677 {

    class MapSum {

        private class Node {
            private int val;
            private Map<Character, Node> next;

            private Node(int val) {
                this.val = val;
                this.next = new HashMap<>();
            }

            private Node() {
                this(0);
            }
        }

        private Node root;

        public MapSum() {
            root = new Node();
        }

        public void insert(String key, int val) {
            Node node = root;
            for (int i = 0; i < key.length(); i++) {
                char ch = key.charAt(i);
                if (node.next.get(ch) == null) {
                    node.next.put(ch, new Node());
                }
                node = node.next.get(ch);
            }
            node.val = val;
        }

        public int sum(String prefix) {
            Node node = searchPrefix(prefix);
            if (node == null) {
                return 0;
            }
            return sumNode(node);
        }

        private Node searchPrefix(String prefix) {
            Node node = root;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                if (node.next.get(ch) == null) {
                    return null;
                }
                node = node.next.get(ch);
            }
            return node;
        }

        private int sumNode(Node node) {
            if (node == null) {
                return 0;
            }
            int sum = node.val;
            for (char ch : node.next.keySet()) {
                sum += sumNode(node.next.get(ch));
            }
            return sum;
        }

    }

}
